#include <iostream>
using namespace std;

template<class K, class V>
struct BSTreeNode {
	BSTreeNode<K, V>* left;
	BSTreeNode<K, V>* right;
	K _key;
	V _value;
	
	BSTreeNode(K key,V value)
		:left(nullptr)
		,right(nullptr)
		,_key(key)
		,_value(value){}

	
};

template<class K, class V>
class BSTree
{
	typedef BSTreeNode<K, V> Node;
public:
	bool Insert(const K& key, const V& value) {
		if (_root == nullptr) {
			_root =new Node(key, value);
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur) {
			if ( key>cur->_key) {
				parent = cur;
				cur = cur->right;
			}
			else if(key <cur->_key){
				parent = cur;
				cur = cur->left;
			}
			else {
				return false;
			}
		}
		if (parent->_key >key) {
			parent->left = new Node(key, value);
		}
		else {
			parent->right = new Node(key, value);
		}
		return true;
	}

	Node* Find(const K& key) {
		Node* cur = _root;
		while (cur) {
			if (key < cur->_key) {
				cur = cur->left;
			}
			else if (key > cur->_key) {
				cur = cur->right;
			}
			else {
				return cur;
			}
		}
		return nullptr;
	}

	bool Erase(const K& key) {
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur) {
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->left;
			}
			else
			{
				if (cur->left == nullptr) {
					if (cur == _root)
					{
						_root = cur->right;
					}
					else {
					if (parent->left == cur) {
						parent->left = cur->right;
						delete cur;
						
					}
					else {
						parent->right = cur->right;
						delete cur;
						
					}
				}
				}
				else if (cur->right == nullptr) {
					if (cur == _root)
					{
						_root = cur->left;
					}
					else {
					if (parent->left == cur) {
						parent->left = cur->left;
						delete cur;
					}
					else {
						parent->right = cur->left;
						delete cur;
					}
				}
				}
				else {
					Node* replaceParent = cur;
					Node* replace = cur->right;
					while (replace->left) {
						replaceParent = replace;
						replace = replace->left;
					}
					cur->_key = replace->_key;
					if (replaceParent->left == replace)
						replaceParent->left = replace->right;
					else
						replaceParent->right = replace->right;
					delete replace;
					
				}
				return true;
				
			}
		}
		return false;
	}

	
	void InOrder() {
		_InOrder(_root);
		cout << endl;
	}
private:
	Node* _root = nullptr;
	void _InOrder(Node* root) {
		if (root == nullptr) {

			return;
		}
		_InOrder(root->left);
		cout << root->_key <<":" << root->_value << " " ;
		_InOrder(root->right);
	}
	void Destroy(Node* root)
	{
		if (root == nullptr)
			return;

		Destroy(root->_left);
		Destroy(root->_right);
		delete root;
	}
};

